package datastructure.matrix;

/**
 *     
 *  The matix should be N * N
 * 
 * 
 * 
                           1 2 3
     (Input)        3 -->  4 5 6  
                           7 8 9

      Output          --> 1 2 4 7 5 3 6 8 9
 * 
 * 
 * 
 * @author Lei
 */
public class PrintMatrixInZigzagOrder {

    
    public static void printMatrixInZigzagOrder(int[][] m) {
        boolean diagnoalDirection = false;
        for (int i = 0; i < m.length; i++) {
            printDiagnoal(0, i, m, diagnoalDirection);
            diagnoalDirection = !diagnoalDirection;
        }

        for (int j = 1; j < m.length; j++) {
            printDiagnoal(j, m.length - 1, m, diagnoalDirection);
            diagnoalDirection = !diagnoalDirection;
        }

    }

    private static void printDiagnoal(int startIndex, int endIndex, int[][] m, boolean diagnoalDirection) {
        if (diagnoalDirection) {
            for (int k = startIndex, n = endIndex; k <= endIndex; k++, n--) {
                System.out.println(m[k][n]);
            }
        }
        else {
            for (int p = endIndex, t = startIndex; p >= startIndex; p--, t++) {
                System.out.println(m[p][t]);
            }
        }
    }

    public static void main(String[] args) {
       int m[][] = {
            {1, 2, 3, 4},
            {8, 7, 6, 5},
            {9, 10, 11, 12},
            {13, 14, 15, 16}
        };
               
        PrintMatrixInZigzagOrder.printMatrixInZigzagOrder(m);
    }
}
